#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    typedef pair<int, int> PII;
    typedef long long LL;
    const LL LLmax = 3e13 + 10;
    const LL mod = 1e9 + 7;
    int countPaths(int n, vector<vector<int>>& roads) {
        vector<vector<PII>> g(n);
        for (auto it : roads) {
            int a = it[0], b = it[1], w = it[2];
            g[a].push_back({ w,b });
            g[b].push_back({ w,a });
        }
        vector<bool>st(n, false);
        vector<LL> dist(n);
        vector<LL> w(n);
        priority_queue<PII, vector<PII>, greater<PII>>q;
        for (int i = 0; i < n; i++) { dist[i] = LLmax; };
        q.push({ 0,0 });
        dist[0] = 0;
        w[0] = 1;
        while (!q.empty()) {
            auto it = q.top();
            q.pop();

            LL d = it.first;
            int u = it.second;
            if (st[u])continue;
            st[u] = true;

            for (auto path : g[u]) {
                LL s = path.first;
                LL v = path.second;
                if (dist[v] > dist[u] + s) {
                    dist[v] = dist[u] + s;
                    w[v] = w[u];
                    q.push({ dist[v],v });
                }
                else if (dist[v] == dist[u] + s) {
                    w[v] = (w[u] + w[v]) % mod;
                }
            }
        }
        return w[n - 1];

    }
};